package BTREE;

/**
 * Description:
 * User:岁亮亮
 * Date:2025-03-25
 * TIME:14:31
 */
public class MyBTREE {

    //三叉树
    public static final int M = 3;
    static class BTRNode{
        int[] keys;
        BTRNode[] btrNodes;
        BTRNode parent;
        int usedSize;
        public BTRNode(){
            //为了分裂方便 一个M叉树最多可以有M个数据 M+1个孩子
            this.keys = new int[M];
            this.btrNodes = new BTRNode[M+1];
        }

    }

    public BTRNode root;

    public boolean insert(int key){
        //root 中没有存入元素时
        if(root == null){
            root = new BTRNode();
            root.keys[0] = key;
            root.usedSize++;
            return true;
        }
        //B树中有元素首先判断要插入的元素是否存在 再进行插入
        Pair<BTRNode,Integer> pair = findBTRNode(key);
        if(pair.getValue() != -1){
            return false;
        }
        //不存在 在要插入的节点插入关键字
        BTRNode btrNode = pair.getKey();
        int index = btrNode.usedSize - 1;
        //用插入排序 插入新的关键字
        for(; index >= 0; index--){
            if(btrNode.keys[index] >= key){
                btrNode.keys[index+1] = btrNode.keys[index];
            }
            else {
                break;
            }

        }
        btrNode.keys[index+1] = key;
        btrNode.usedSize++;
        //不处理孩子 因为你每次插入都是在叶子节点进行插入
        //判断是否要进行分裂 usedSize >= M 就是在有M-1个关键字时插入进去 这是有M个关键字 进行分裂
        if(btrNode.usedSize < M){
            return true;
        }
        else{
            //进行分裂 整个分裂过程当中,会一直向上分裂,直到根节点分裂结束为止
            split(btrNode);
            return true;
        }
    }
    /**
     * 1 申请新节点
     * 2.找到分裂节点的中间位置
     * 3.分裂节点的中间位置右边的元素及孩子移动新节点中
     * 4.新节点和分裂节点的中间位置 往该节点的父亲节点中插入
     */
    private void split(BTRNode btrNode) {
        BTRNode newBtrNode = new BTRNode();
        BTRNode cur = btrNode;
        BTRNode parent = cur.parent;
        int mid = cur.usedSize >> 1;
        int i = mid + 1;
        int j = 0;
        for(; i < cur.usedSize; i++){
            newBtrNode.keys[j] = cur.keys[i];
            newBtrNode.btrNodes[j] = cur.btrNodes[i];
            if(newBtrNode.btrNodes[j] != null){
                newBtrNode.btrNodes[j].parent = newBtrNode;
            }
            j++;
        }
        newBtrNode.btrNodes[j] = cur.btrNodes[i];
        if(newBtrNode.btrNodes[j] != null){
            newBtrNode.btrNodes[j].parent = newBtrNode;
        }
        cur.usedSize = cur.usedSize - j - 1;
        newBtrNode.usedSize = j;

        if(parent == null){
            root = new BTRNode();
            root.keys[0] = cur.keys[mid];
            root.btrNodes[0] = cur;
            root.btrNodes[1] = newBtrNode;
            root.usedSize = 1;
            cur.parent = root;
            newBtrNode.parent = root;

        }
        else {
            newBtrNode.parent = parent;

            int midVal = cur.keys[mid];
            int pIndex = parent.usedSize-1;
            for(; pIndex >= 0; pIndex--){
                if(parent.keys[pIndex] >= midVal){
                    parent.keys[pIndex+1] = parent.keys[pIndex];
                    parent.btrNodes[pIndex+2] = parent.btrNodes[pIndex+1];
                }
                else{
                    break;
                }
            }
            parent.keys[pIndex+1] = midVal;
            parent.btrNodes[pIndex+2] = newBtrNode;
            parent.usedSize++;
            if(parent.usedSize >= M){
                split(parent);
            }
        }





    }

    /**
     *  返回值
     *  1.下标 -1表示不存在 1 表示存在 . 但不存在时想要返回要插入的节点 下标就不可以
     *  2 节点 有两种
     *  2.1存在时 返回cur  不存在时返回parent要插入的节点 但cur和parent 不能判断出是否存在
     *  2.2存在时返回 null 不存在返回parent
     *  3.再2.2中想要在存在时不想返回null 要返回cur 而且又能判断出是否存在 可以在一个<K,V>类</K,V>
     *  K存放cur val存放 i   i = -1表示不存在 i = 1 时表示存在
     *  也可以用hashMap替代 但他还要查找   而pair<K,V>类只需要判断getVal的值就可以
     * @param key
     * @return
     */
    private Pair<BTRNode,Integer>  findBTRNode(int key) {
        BTRNode cur = root;
        BTRNode parent = null;
        while(cur != null){
            int index = 0;
            while(index < cur.usedSize){
                if(cur.keys[index] == key){
                    //存在
                    return new Pair<>(cur,1);
                }
                else if(cur.keys[index] < key){
                    index++;
                }
                else {
                    //该节点中不存在key 向下继续查找
                    break;
                }
            }
            parent = cur;
            cur = cur.btrNodes[index];
        }
        return new Pair<>(parent,-1);
    }
    public void inorder(BTRNode root){
        if(root == null){
            return;
        }
        for(int i = 0; i < root.usedSize; i++){
            inorder(root.btrNodes[i]);
            System.out.println(root.keys[i]);
        }
        inorder(root.btrNodes[root.usedSize]);

    }

    public static void main(String[] args) {
        MyBTREE btree = new MyBTREE();
        int[] array = {53,139,75,49,145,36,101};
        for (int i = 0; i < array.length; i++) {
            btree.insert(array[i]);
        }
        System.out.println("dddd");
        //btree.inorder(btree.root);

    }


}
